from collections import Counter
from collections import defaultdict
def solve_test_case(n, numbers):
cnt = defaultdict(int)
res=0
d= (1<<31)-1
for nb in numbers:
inv=d^nb
if cnt[inv]>0:
cnt[inv]-=1
else:
cnt[nb]+=1
res+=1
return res
if __name__ == "__main__":
t = int(input())
test_cases = []
for _ in range(t):
n = int(input())
numbers = list(map(int, input().split()))
print(solve_test_case(n, numbers))#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int>a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int v=(1<<31)-1;
map<int, vector<int>>mp;
for (int i = 0; i < n; i++) {
mp[a[i]].push_back(i);
}
vector<int>visited(n, 0);
for (int i = 0; i < n; i++) {
if (visited[i])continue;
int number = a[i]^v;
if (mp[number].size() > 0 && mp[a[i]].size() > 0) {
int s1 = mp[number].size();
int s2 = mp[a[i]].size();
int mn = min(s1, s2);
while (mn--) {
int l = mp[a[i]].back();
visited[l] = 1;
mp[a[i]].pop_back();
int index = mp[number].back();
visited[index] = 1;
mp[number].pop_back();
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
if (visited[i] == 1) {
count++;
}
}
int remaining = n - count;
int ans = remaining + count / 2;
cout << ans << endl;
}
int main()
{
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
int t;
cin >> t;
while (t--) {
solve();
}
}380C - Sereja and Brackets | 1281B - Azamon Web Services |
1702A - Round Down the Price | 1681C - Double Sort |
12A - Super Agent | 1709A - Three Doors |
1680C - Binary String | 1684B - Z mod X = C |
1003A - Polycarp's Pockets | 1691B - Shoe Shuffling |
1706A - Another String Minimization Problem | 1695B - Circle Game |
1702B - Polycarp Writes a String from Memory | 1701A - Grass Field |
489C - Given Length and Sum of Digits | 886B - Vlad and Cafes |
915A - Garden | 356A - Knight Tournament |
1330A - Dreamoon and Ranking Collection | 1692B - All Distinct |
1156C - Match Points | 1675A - Food for Animals |
1328C - Ternary XOR | 1689A - Lex String |
1708B - Difference of GCDs | 863A - Quasi-palindrome |
1478A - Nezzar and Colorful Balls | 1581B - Diameter of Graph |
404A - Valera and X | 908A - New Year and Counting Cards |